package com.datastructure.algorithm.KMP;
//KMP匹配算法
//先得到字串的部分匹配表
//暴力匹配算法的升级，通过字符串内部的字符差异特点减少比较的次数
public class KMPAlgorithm {

    public static void main(String[] args) {

    }

    public static int kmpSearch(String str1,String str2, int[] next){

        // 遍历
        for(int i = 0,j=0;i<str1.length();i++){
            // 需要处理str1.charAt(i) != str2.charAt,去调整j的大小
            // KMP算法核心点，可以验证。。。
            while (j>0&&str1.charAt(i) != str2.charAt(j)){
                j = next[j-1];
            }
            if(str1.charAt(i)==str2.charAt(j)){
                j++;
            }
            if(j == str2.length()){
                return i - j + 1;
            }
        }
        return -1;
    }

    // 获取一个字符串(字串)的部分匹配值列表
    public static int[] KmpNext(String dest){
        // 创建一个next数组保存部分匹配值
        int[] next = new int[dest.length()];
        next[0] = 0; // 如果字符串是长度为1，部分匹配值就是0
        for(int i =1,j = 0;i < dest.length();i++){
            // 当dest.charAt(i) != dest.charAt(j)，我们需要从next[j-1]获取新的j
            // 直到我们发现有dest.charAt(i) == dest.charAt(j)成立才退出
            // 这是KMP算法的核心点
            while (j > 0 && dest.charAt(i) != dest.charAt(j)){
                j = next[j-1];
            }
            if(dest.charAt(i) == dest.charAt(j)){
                j++;
            }
            next[i] = j;
        }
        return next;
    }

    //牛客网
    public int kmp (String S, String T) {
        //特殊情况判断
        int m=S.length(),n=T.length();
        if(m>n||n==0) return 0;

        //初始化计数，获取next数组
        int cnt=0;
        int[] next=getNext(S);

        //遍历主串和模式串
        for(int i=0,j=0;i<n;i++){
            //只要不相等，回退到next数组记录的下一位
            while(j>0&&T.charAt(i)!=S.charAt(j)){
                j=next[j-1];
            }
            if(T.charAt(i)==S.charAt(j)) j++;
            //如果j为m，说明完全匹配一次
            if(j==m){
                //计数加一，索引回退到next数组记录的下一位
                cnt++;
                j=next[j-1];
            }
        }
        return cnt;
    }

    //确定next数组
    private int[] getNext(String S){
        int m=S.length();
        int[] next=new int[m];
        for(int i=1,j=0;i<m;i++){
            //只要不相等，回退到next数组记录的下一位
            while(j>0&&S.charAt(i)!=S.charAt(j)){
                j=next[j-1];
            }
            //前缀索引后移
            if(S.charAt(i)==S.charAt(j)) j++;
            //确定应该回退到的下一个索引
            next[i]=j;
        }
        return next;
    }
}

